//
// Created by JinBaotong on 2024/12/11.
//
#include "trans.h"
#include<fstream>
#include <algorithm>
#include <chrono>

TRANS::TRANS(std::string filename) {
    std::ifstream infile(filename);
    int u, v;
    std::string help;
    time_t t, w = 1;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            cntplus++;
            tEdge e = {cntplus, {u, t, OUT}, {v, t + w, IN}, w};
            edges[cntplus] = e;
            outedges[{u, t, OUT}].emplace(cntplus);
            inedges[{v, t + w, IN}].emplace(cntplus);
            outtimes[u].emplace(t);
            intimes[v].emplace(t + w);
            degree[{u, t, OUT}]++;
            degree[{v, t + w, IN}]++;
        }
    }
    for (auto& [node, times]: intimes) {
        for (auto it = times.begin(); it != times.end(); it++) {
            if (next(it) != times.end()) {
                cntminus--;
                tEdge e = {cntminus, {node, *it, IN}, {node, *next(it), IN}, 0};
                edges[cntminus] = e;
                outedges[{node, *it, IN}].emplace(cntminus);
                inedges[{node, *next(it), IN}].emplace(cntminus);
                iicheck[{node, *it, IN}] = cntminus;
            }
        }
        for (auto it = times.rbegin(); it != times.rend(); it++) {
            if (!outtimes.contains(node))   continue;
            auto it2 = outtimes[node].lower_bound(*it);
            if (it2 != outtimes[node].end()) {
                if (iocheck.contains({node, *it2, OUT}))    continue;
                cntminus--;
                tEdge e = {cntminus, {node, *it, IN}, {node, *it2, OUT}, 0};
                edges[cntminus] = e;
                outedges[{node, *it, IN}].emplace(cntminus);
                inedges[{node, *it2, OUT}].emplace(cntminus);
                iocheck[{node, *it, IN}] = cntminus;
                iocheck[{node, *it2, OUT}] = cntminus;
            }
        }
    }
    for (auto& [node, times]: outtimes) {
        for (auto it = times.begin(); it != times.end(); it++) {
            if (next(it) != times.end()) {
                cntminus--;
                tEdge e = {cntminus, {node, *it, OUT}, {node, *next(it), OUT}, 0};
                edges[cntminus] = e;
                outedges[{node, *it, OUT}].emplace(cntminus);
                inedges[{node, *next(it), OUT}].emplace(cntminus);
                iicheck[{node, *it, OUT}] = cntminus;
            }
        }
    }
}

void TRANS::caculate(int x, time_t ta, time_t to) {
    f.clear();
    dis.clear();
    source = x;
    start = ta;
    end = to;
    if (outtimes.contains(x)) {
        for (auto it = outtimes[x].lower_bound(ta); it != outtimes[x].end(); it++) {
            if (*it > to) break;
            pq.emplace(0, *it, OUT, x, 0);
        }
    }
    while (!pq.empty()) {
        auto [d, t, io, u, eid] = pq.top();
        pq.pop();
        if (dis.contains({u, t, io}))   continue;
        dis[{u, t, io}] = d;
        parent_edge[{u, t, io}] = eid;
        parent_node[{u, t, io}] = edges[eid].u;
        children[edges[eid].u].emplace(u, t, io);
        if (!f.contains(u)) f[u] = d;
        if (!outedges.contains({u, t, io})) continue;
        for (auto neid: outedges[{u, t, io}]) {
            tEdge& e = edges[neid];
            if (dis.contains(e.v))  continue;
            auto [vnode, vtime, vio] = e.v;
            if (vtime >= ta && vtime <= to) {
                pq.emplace(d + e.w, vtime, vio, vnode, neid);
            }
        }
    }
    f[x] = 0;
}

void TRANS::add_edges(std::vector<Edge>& new_edges) {
    std::vector<tEdge> add_edges;
    std::vector<tEdge> delete_edges;
    std::map<int, std::set<int>> tintimes, touttimes;
    for (auto &e: new_edges) {
        cntplus++;
        tEdge te = {cntplus, {e.u, e.t, OUT}, {e.v, e.w + e.t, IN}, e.w};
        edges[cntplus] = te;
        add_edges.emplace_back(te);
        outedges[te.u].emplace(cntplus);
        inedges[te.v].emplace(cntplus);
        if (!outtimes.contains(e.t)) {
            touttimes[e.u].emplace(e.t);
            outtimes[e.u].emplace(e.t);
        }
        if (!intimes.contains(e.w + e.t)) {
            tintimes[e.v].emplace(e.w + e.t);
            intimes[e.v].emplace(e.w + e.t);
        }
        degree[{e.u, e.t, OUT}]++;
        degree[{e.v, e.w + e.t, IN}]++;
    }
    for (auto& [node, times]: tintimes) {
            for (auto time: times) {
                auto it = intimes[node].lower_bound(time);
                if (it != intimes[node].begin()) {
                    if (!iicheck[{node, time, IN}]) {
                        add_minus_edge(node, *prev(it), IN, node, time, IN, 0);
                        iicheck[{node, *prev(it), IN}] = cntminus;
                        add_edges.push_back(edges[cntminus]);
                    }
                    else {
                        tEdge& te = edges[iicheck[{node, time, IN}]];
                        if (std::get<1>(te.v) == time) continue;
                        delete_edges.push_back(te);
                        add_minus_edge(node, *prev(it), IN, node, time, IN, 0);
                        iicheck[{node, *prev(it), IN}] = cntminus;
                        add_edges.push_back(edges[cntminus]);
                    }
                }
                if (next(it) != intimes[node].end()) {
                    add_minus_edge(node, time, IN, node, *next(it), IN, 0);
                    iicheck[{node, time, IN}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            if (outtimes.contains(node)) {
                for (auto it = times.rbegin(); it != times.rend(); it++) {
                    time_t time = *it;
                    auto it2 = outtimes[node].lower_bound(time);
                    if (it2 != outtimes[node].end()) {
                        if (iocheck.contains({node, *it2, OUT})) {
                            tEdge& te = edges[iocheck[{node, *it2, OUT}]];
                            if (std::get<1>(te.u) < time) {
                                delete_edges.push_back(te);
                                iocheck.erase(te.u);
                                add_minus_edge(node, time, IN, node, *it2, OUT, 0);
                                iocheck[{node, time, IN}] = cntminus;
                                iocheck[{node, *it2, OUT}] = cntminus;
                                add_edges.push_back(edges[cntminus]);
                            }
                        }
                        else {
                            add_minus_edge(node, time, IN, node, *it2, OUT, 0);
                            iocheck[{node, time, IN}] = cntminus;
                            iocheck[{node, *it2, OUT}] = cntminus;
                            add_edges.push_back(edges[cntminus]);
                        }
                    }
                }
            }
        }
    for (auto& [node, times]: touttimes) {
            for (auto time: times) {
                auto it = outtimes[node].lower_bound(time);
                if (it != outtimes[node].begin()) {
                    if (!iicheck[{node, time, OUT}]) {
                        add_minus_edge(node, *prev(it), OUT, node, time, OUT, 0);
                        iicheck[{node, *prev(it), OUT}] = cntminus;
                        add_edges.push_back(edges[cntminus]);
                    }
                    else {
                        tEdge& te = edges[iicheck[{node, time, OUT}]];
                        if (std::get<1>(te.v) == time) continue;
                        delete_edges.push_back(te);
                        add_minus_edge(node, *prev(it), OUT, node, time, OUT, 0);
                        iicheck[{node, *prev(it), OUT}] = cntminus;
                        add_edges.push_back(edges[cntminus]);
                    }
                }
                if (next(it) != outtimes[node].end()) {
                    add_minus_edge(node, time, OUT, node, *next(it), OUT, 0);
                    iicheck[{node, time, OUT}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            if (intimes.contains(node)) {
                for (auto it = times.begin(); it != times.end(); it++) {
                    time_t time = *it;
                    auto it2 = intimes[node].upper_bound(time);
                    if (it2 != intimes[node].begin()) {
                        if (iocheck.contains({node, *prev(it2), IN})) {
                            tEdge& te = edges[iocheck[{node, *prev(it2), IN}]];
                            if (std::get<1>(te.v) > time) {
                                delete_edges.push_back(te);
                                iocheck.erase(te.v);
                                add_minus_edge(node, *prev(it2), IN, node, time, OUT, 0);
                                iocheck[{node, *prev(it2), IN}] = cntminus;
                                iocheck[{node, time, OUT}] = cntminus;
                                add_edges.push_back(edges[cntminus]);
                            }
                        }
                        else {
                            add_minus_edge(node, *prev(it2), IN, node, time, OUT, 0);
                            iocheck[{node, *prev(it2), IN}] = cntminus;
                            iocheck[{node, time, OUT}] = cntminus;
                            add_edges.push_back(edges[cntminus]);
                        }
                    }
                }
            }
        }
    dynamic_add_edges(add_edges);
    for (auto &e: delete_edges) {
        edges.erase(e.id);
        outedges[e.u].erase(e.id);
        inedges[e.v].erase(e.id);
    }
    dynamic_delete_edges(delete_edges);
}

void TRANS::add_minus_edge(int unode, time_t utime, inout uio, int vnode, time_t vtime, inout vio, time_t w) {
    cntminus--;
    tEdge e = {cntminus, {unode, utime, uio}, {vnode, vtime, vio}, w};
    edges[cntminus] = e;
    outedges[e.u].emplace(cntminus);
    inedges[e.v].emplace(cntminus);
}

void TRANS::delete_edges(std::vector<Edge> &old_edges) {
    std::vector<tEdge> add_edges;
    std::vector<tEdge> delete_edges;
    std::set<int> an;
    for (auto &e: old_edges) {
        delete_edges.push_back({e.id, {e.u, e.t, OUT}, {e.v, e.t + e.w, IN}, e.w});
        degree[{e.u, e.t, OUT}]--;
        if (degree[{e.u, e.t, OUT}] == 0) {
            outtimes[e.u].erase(e.t);
            an.emplace(e.u);
            if (iicheck.contains({e.u, e.t, OUT})) {
                tEdge& te = edges[iicheck[{e.u, e.t, OUT}]];
                delete_edges.push_back(te);
                iicheck.erase({e.u, e.t, OUT});
            }
            if (iocheck.contains({e.u, e.t, OUT})) {
                tEdge& te = edges[iocheck[{e.u, e.t, OUT}]];
                delete_edges.push_back(te);
                iocheck.erase(te.u);
                iocheck.erase(te.v);
            }
        }
        degree[{e.v, e.t + e.w, IN}]--;
        if (degree[{e.v, e.t + e.w, IN}] == 0) {
            intimes[e.v].erase(e.t + e.w);
            an.emplace(e.v);
            if (iicheck.contains({e.v, e.t + e.w, IN})) {
                tEdge& te = edges[iicheck[{e.v, e.t + e.w, IN}]];
                delete_edges.push_back(te);
                iicheck.erase({e.v, e.t + e.w, IN});
            }
            if (iocheck.contains({e.v, e.t + e.w, IN})) {
                tEdge& te = edges[iocheck[{e.v, e.t + e.w, IN}]];
                delete_edges.push_back(te);
                iocheck.erase(te.u);
                iocheck.erase(te.v);
            }
        }
    }
    for (auto& node: an) {
        for (auto it = outtimes[node].begin(); it != outtimes[node].end(); it++) {
            if (iicheck.contains({node, *it, OUT})) {
                tEdge& te = edges[iicheck[{node, *it, OUT}]];
                if (next(it) == outtimes[node].end()) {
                    delete_edges.push_back(te);
                    iicheck.erase({node, *it, OUT});
                }
                else if (std::get<1>(te.v) != *next(it)) {
                    delete_edges.push_back(te);
                    add_minus_edge(node, *it, OUT, node, *next(it), OUT, 0);
                    iicheck[{node, *it, OUT}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            else {
                if (next(it) != outtimes[node].end()) {
                    add_minus_edge(node, *it, OUT, node, *next(it), OUT, 0);
                    iicheck[{node, *it, OUT}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
        }
        for (auto it = intimes[node].begin(); it != intimes[node].end(); it++) {
            if (iicheck.contains({node, *it, IN})) {
                tEdge& te = edges[iicheck[{node, *it, IN}]];
                if (next(it) == intimes[node].end()) {
                    delete_edges.push_back(te);
                    iicheck.erase({node, *it, IN});
                }
                else if (std::get<1>(te.v) != *next(it)) {
                    delete_edges.push_back(te);
                    add_minus_edge(node, *it, IN, node, *next(it), IN, 0);
                    iicheck[{node, *it, IN}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            else {
                if (next(it) != intimes[node].end()) {
                    add_minus_edge(node, *it, IN, node, *next(it), IN, 0);
                    iicheck[{node, *it, IN}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
        }
        for (auto it = intimes[node].rbegin(); it != intimes[node].rend(); it++) {
            auto it2 = outtimes[node].lower_bound(*it);
            if (it2 == outtimes[node].end())   continue;
            if (iocheck.contains({node, *it2, OUT}))    continue;
            add_minus_edge(node, *it, IN, node, *it2, OUT, 0);
            iocheck[{node, *it, IN}] = cntminus;
            iocheck[{node, *it2, OUT}] = cntminus;
            add_edges.push_back(edges[cntminus]);
        }
    }
    dynamic_add_edges(add_edges);
    for (auto &e: delete_edges) {
        edges.erase(e.id);
        outedges[e.u].erase(e.id);
        inedges[e.v].erase(e.id);
    }
    dynamic_delete_edges(delete_edges);
}

void TRANS::dynamic_add_edges(std::vector<tEdge> new_edges) {
    for (auto &e: new_edges) {
        if (std::get<0>(e.u) == source && std::get<1>(e.u) >= start && std::get<1>(e.u) <= end) dis[e.u] = 0;
        if (!dis.contains(e.u)) continue;
        if (std::get<1>(e.u) >= start && std::get<1>(e.v) <= end) {
            if (!dis.contains(e.v) || dis[e.v] > dis[e.u] + e.w) {
                pq.emplace(dis[e.u] + e.w, std::get<1>(e.v), std::get<2>(e.v), std::get<0>(e.v), e.id);
            }
        }
    }
    while (!pq.empty()) {
        auto [d, t, io, node, eid] = pq.top();
        pq.pop();
        if (dis.contains({node, t, io}) && dis[{node, t, io}] <= d) continue;
        dis[{node, t, io}] = d;
        children[edges[parent_edge[{node, t, io}]].u].erase({node, t, io});
        parent_edge[{node, t, io}] = eid;
        parent_node[{node, t, io}] = edges[parent_edge[{node, t, io}]].u;
        children[edges[eid].u].emplace(node, t, io);
        if (!f.contains(node) || f[node] > d)   f[node] = d;
        if (outedges.contains({node, t, io})) {
            for (auto neid: outedges[{node, t, io}]) {
                tEdge& te = edges[neid];
                if (std::get<1>(te.u) >= start && std::get<1>(te.v) <= end) {
                    if (!dis.contains(te.v) || dis[te.v] > dis[te.u] + te.w) {
                        pq.emplace(dis[te.u] + te.w, std::get<1>(te.v), std::get<2>(te.v), std::get<0>(te.v), te.id);
                    }
                }
            }
        }
    }
}

void TRANS::re_add_edges(std::vector<Edge> new_edges) {
    std::vector<tEdge> add_edges;
    std::vector<tEdge> delete_edges;
    std::map<int, std::set<int>> tintimes, touttimes;
    for (auto &e: new_edges) {
        cntplus++;
        tEdge te = {cntplus, {e.u, e.t, OUT}, {e.v, e.w + e.t, IN}, e.w};
        edges[cntplus] = te;
        add_edges.emplace_back(te);
        outedges[te.u].emplace(cntplus);
        inedges[te.v].emplace(cntplus);
        if (!outtimes.contains(e.t)) {
            touttimes[e.u].emplace(e.t);
            outtimes[e.u].emplace(e.t);
        }
        if (!intimes.contains(e.w + e.t)) {
            tintimes[e.v].emplace(e.w + e.t);
            intimes[e.v].emplace(e.w + e.t);
        }
        degree[{e.u, e.t, OUT}]++;
        degree[{e.v, e.w + e.t, IN}]++;
    }
    for (auto& [node, times]: tintimes) {
        for (auto time: times) {
            auto it = intimes[node].lower_bound(time);
            if (it != intimes[node].begin()) {
                if (!iicheck[{node, time, IN}]) {
                    add_minus_edge(node, *prev(it), IN, node, time, IN, 0);
                    iicheck[{node, *prev(it), IN}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
                else {
                    tEdge& te = edges[iicheck[{node, time, IN}]];
                    if (std::get<1>(te.v) == time) continue;
                    delete_edges.push_back(te);
                    add_minus_edge(node, *prev(it), IN, node, time, IN, 0);
                    iicheck[{node, *prev(it), IN}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            if (next(it) != intimes[node].end()) {
                add_minus_edge(node, time, IN, node, *next(it), IN, 0);
                iicheck[{node, time, IN}] = cntminus;
                add_edges.push_back(edges[cntminus]);
            }
        }
        if (outtimes.contains(node)) {
            for (auto it = times.rbegin(); it != times.rend(); it++) {
                time_t time = *it;
                auto it2 = outtimes[node].lower_bound(time);
                if (it2 != outtimes[node].end()) {
                    if (iocheck.contains({node, *it2, OUT})) {
                        tEdge& te = edges[iocheck[{node, *it2, OUT}]];
                        if (std::get<1>(te.u) < time) {
                            delete_edges.push_back(te);
                            iocheck.erase(te.u);
                            add_minus_edge(node, time, IN, node, *it2, OUT, 0);
                            iocheck[{node, time, IN}] = cntminus;
                            iocheck[{node, *it2, OUT}] = cntminus;
                            add_edges.push_back(edges[cntminus]);
                        }
                    }
                    else {
                        add_minus_edge(node, time, IN, node, *it2, OUT, 0);
                        iocheck[{node, time, IN}] = cntminus;
                        iocheck[{node, *it2, OUT}] = cntminus;
                        add_edges.push_back(edges[cntminus]);
                    }
                }
            }
        }
    }
    for (auto& [node, times]: touttimes) {
        for (auto time: times) {
            auto it = outtimes[node].lower_bound(time);
            if (it != outtimes[node].begin()) {
                if (!iicheck[{node, time, OUT}]) {
                    add_minus_edge(node, *prev(it), OUT, node, time, OUT, 0);
                    iicheck[{node, *prev(it), OUT}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
                else {
                    tEdge& te = edges[iicheck[{node, time, OUT}]];
                    if (std::get<1>(te.v) == time) continue;
                    delete_edges.push_back(te);
                    add_minus_edge(node, *prev(it), OUT, node, time, OUT, 0);
                    iicheck[{node, *prev(it), OUT}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            if (next(it) != outtimes[node].end()) {
                add_minus_edge(node, time, OUT, node, *next(it), OUT, 0);
                iicheck[{node, time, OUT}] = cntminus;
                add_edges.push_back(edges[cntminus]);
            }
        }
        if (intimes.contains(node)) {
            for (auto it = times.begin(); it != times.end(); it++) {
                time_t time = *it;
                auto it2 = intimes[node].upper_bound(time);
                if (it2 != intimes[node].begin()) {
                    if (iocheck.contains({node, *prev(it2), IN})) {
                        tEdge& te = edges[iocheck[{node, *prev(it2), IN}]];
                        if (std::get<1>(te.v) > time) {
                            delete_edges.push_back(te);
                            iocheck.erase(te.v);
                            add_minus_edge(node, *prev(it2), IN, node, time, OUT, 0);
                            iocheck[{node, *prev(it2), IN}] = cntminus;
                            iocheck[{node, time, OUT}] = cntminus;
                            add_edges.push_back(edges[cntminus]);
                        }
                    }
                    else {
                        add_minus_edge(node, *prev(it2), IN, node, time, OUT, 0);
                        iocheck[{node, *prev(it2), IN}] = cntminus;
                        iocheck[{node, time, OUT}] = cntminus;
                        add_edges.push_back(edges[cntminus]);
                    }
                }
            }
        }
    }
    for (auto &e: delete_edges) {
        edges.erase(e.id);
        outedges[e.u].erase(e.id);
        inedges[e.v].erase(e.id);
    }
    caculate(source, start, end);
}

void TRANS::re_delete_edges(std::vector<Edge> old_edges) {
    std::vector<tEdge> add_edges;
    std::vector<tEdge> delete_edges;
    std::set<int> an;
    for (auto &e: old_edges) {
        delete_edges.push_back({e.id, {e.u, e.t, OUT}, {e.v, e.t + e.w, IN}, e.w});
        degree[{e.u, e.t, OUT}]--;
        if (degree[{e.u, e.t, OUT}] == 0) {
            outtimes[e.u].erase(e.t);
            an.emplace(e.u);
            if (iicheck.contains({e.u, e.t, OUT})) {
                tEdge& te = edges[iicheck[{e.u, e.t, OUT}]];
                delete_edges.push_back(te);
                iicheck.erase({e.u, e.t, OUT});
            }
            if (iocheck.contains({e.u, e.t, OUT})) {
                tEdge& te = edges[iocheck[{e.u, e.t, OUT}]];
                delete_edges.push_back(te);
                iocheck.erase(te.u);
                iocheck.erase(te.v);
            }
        }
        degree[{e.v, e.t + e.w, IN}]--;
        if (degree[{e.v, e.t + e.w, IN}] == 0) {
            intimes[e.v].erase(e.t + e.w);
            an.emplace(e.v);
            if (iicheck.contains({e.v, e.t + e.w, IN})) {
                tEdge& te = edges[iicheck[{e.v, e.t + e.w, IN}]];
                delete_edges.push_back(te);
                iicheck.erase({e.v, e.t + e.w, IN});
            }
            if (iocheck.contains({e.v, e.t + e.w, IN})) {
                tEdge& te = edges[iocheck[{e.v, e.t + e.w, IN}]];
                delete_edges.push_back(te);
                iocheck.erase(te.u);
                iocheck.erase(te.v);
            }
        }
    }
    for (auto& node: an) {
        for (auto it = outtimes[node].begin(); it != outtimes[node].end(); it++) {
            if (iicheck.contains({node, *it, OUT})) {
                tEdge& te = edges[iicheck[{node, *it, OUT}]];
                if (next(it) == outtimes[node].end()) {
                    delete_edges.push_back(te);
                    iicheck.erase({node, *it, OUT});
                }
                else if (std::get<1>(te.v) != *next(it)) {
                    delete_edges.push_back(te);
                    add_minus_edge(node, *it, OUT, node, *next(it), OUT, 0);
                    iicheck[{node, *it, OUT}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            else {
                if (next(it) != outtimes[node].end()) {
                    add_minus_edge(node, *it, OUT, node, *next(it), OUT, 0);
                    iicheck[{node, *it, OUT}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
        }
        for (auto it = intimes[node].begin(); it != intimes[node].end(); it++) {
            if (iicheck.contains({node, *it, IN})) {
                tEdge& te = edges[iicheck[{node, *it, IN}]];
                if (next(it) == intimes[node].end()) {
                    delete_edges.push_back(te);
                    iicheck.erase({node, *it, IN});
                }
                else if (std::get<1>(te.v) != *next(it)) {
                    delete_edges.push_back(te);
                    add_minus_edge(node, *it, IN, node, *next(it), IN, 0);
                    iicheck[{node, *it, IN}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
            else {
                if (next(it) != intimes[node].end()) {
                    add_minus_edge(node, *it, IN, node, *next(it), IN, 0);
                    iicheck[{node, *it, IN}] = cntminus;
                    add_edges.push_back(edges[cntminus]);
                }
            }
        }
        for (auto it = intimes[node].rbegin(); it != intimes[node].rend(); it++) {
            auto it2 = outtimes[node].lower_bound(*it);
            if (it2 == outtimes[node].end())   continue;
            if (iocheck.contains({node, *it2, OUT}))    continue;
            add_minus_edge(node, *it, IN, node, *it2, OUT, 0);
            iocheck[{node, *it, IN}] = cntminus;
            iocheck[{node, *it2, OUT}] = cntminus;
            add_edges.push_back(edges[cntminus]);
        }
    }
    for (auto &e: delete_edges) {
        edges.erase(e.id);
        outedges[e.u].erase(e.id);
        inedges[e.v].erase(e.id);
    }
    caculate(source, start, end);
}
void TRANS::dynamic_delete_edges(std::vector<tEdge> old_edges) {
    red.clear();
    for (auto &e: old_edges) {
        if (parent_edge.contains(e.v) && parent_edge[e.v] == e.id) {
            pq.emplace(dis[e.v], std::get<1>(e.v), std::get<2>(e.v), std::get<0>(e.v), 0);
        }
    }
    while (!pq.empty()) {
        auto [d, t, io, node, eid] = pq.top();
        pq.pop();
        if (node == source && t >= start && t <= end) {
            children[parent_node[{node, t, io}]].erase({node, t, io});
            dis[{node, t, io}] = 0;
            parent_edge[{node, t, io}] = 0;
            parent_node[{node, t, io}] = {node, t, io};
            continue;
        }
        int bestd = -1, beste = 0;
        if (inedges.contains({node, t, io})) {
            for (auto neid: inedges[{node, t, io}]) {
                auto& te = edges[neid];
                if (red.contains(te.u))     continue;
                if (!dis.contains(te.u))    continue;
                if (std::get<1>(te.u) >= start && std::get<1>(te.v) <= end) {
                    if (bestd == -1 || dis[te.u] + te.w < bestd) {
                        bestd = dis[te.u] + te.w;
                        beste = te.id;
                    }
                }
            }
        }
        if (bestd == d) {
            children[parent_node[{node, t, io}]].erase({node, t, io});
            parent_edge[{node, t, io}] = beste;
            parent_node[{node, t, io}] = edges[beste].u;
            children[edges[beste].u].emplace(node, t, io);
        }
        else {
            red.emplace(node, t, io);
            if (children.contains({node, t, io})) {
                for (auto child: children[{node, t, io}]) {
                    pq.emplace(dis[child], std::get<1>(child), std::get<2>(child), std::get<0>(child), 0);
                }
            }
        }
    }
    std::unordered_set<int> new_red;
    for (auto& rnode: red) {
        auto [node, t, io] = rnode;
        new_red.emplace(node);
        dis.erase(rnode);
        children[parent_node[rnode]].erase(rnode);
        parent_edge.erase(rnode);
        parent_node.erase(rnode);
        children.erase(rnode);
        int bestd = -1, beste = 0;
        if (inedges.contains({node, t, io})) {
            for (auto neid: inedges[{node, t, io}]) {
                auto& te = edges[neid];
                if (red.contains(te.u))     continue;
                if (!dis.contains(te.u))    continue;
                if (std::get<1>(te.u) >= start && std::get<1>(te.v) <= end) {
                    if (bestd == -1 || dis[te.u] + te.w < bestd) {
                        bestd = dis[te.u] + te.w;
                        beste = te.id;
                    }
                }
            }
        }
        if (bestd != -1) {
            pq.emplace(bestd, t, io, node, beste);
        }
    }
    while (!pq.empty()) {
        auto [d, t, io, node, eid] = pq.top();
        pq.pop();
        if (dis.contains({node, t, io}) && dis[{node, t, io}] <= d)  continue;
        dis[{node, t, io}] = d;
        parent_edge[{node, t, io}] = eid;
        parent_node[{node, t, io}] = edges[eid].u;
        children[edges[eid].u].emplace(node, t, io);
        if (outedges.contains({node, t, io})) {
            for (auto neid: outedges[{node, t, io}]) {
                tEdge& te = edges[neid];
                if (std::get<1>(te.u) >= start && std::get<1>(te.v) <= end) {
                    if (!dis.contains(te.v) || dis[te.v] > dis[te.u] + te.w) {
                        pq.emplace(dis[te.u] + te.w, std::get<1>(te.v),std::get<2>(te.v), std::get<0>(te.v), te.id);
                    }
                }
            }
        }
    }
    for (auto& u: new_red) {
        f.erase(u);
        if (intimes.contains(u)) {
            auto it = intimes[u].upper_bound(end);
            if (it != intimes[u].begin()) {
                time_t time = *prev(it);
                if (dis.contains({u, time, IN}))    f[u] = dis[{u, time, IN}];
            }
        }
    }
    f[source] = 0;
}

void static_test(std::string filename) {
    ADJ adj(filename);
    TRANS trans(filename);
    for (int i = 1; i < 100; i++) {
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        trans.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (adj.f.size() != trans.f.size()) {
            std::cout << "error size!!!!!!!!!!!!!" << std::endl;
        }
        for (auto& [node, dis]: adj.f) {
            if (trans.f.contains(node)) {
                if (trans.f[node] != dis) {
                    std::cout << "error dis!!!!!!!!!!!!!" << std::endl;
                }
            } else {
                std::cout << "miss!!!!!!!!!!!!!" << std::endl;
            }
        }
        std::cout << "finish " << i << std::endl;
    }
}

void add_test1(std::string filename) {
    for (int i = 1; i < 100; i++) {
        ADJ adj("");
        OSE ose = adj.to_OSE();
        TRANS trans("");
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        trans.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (infile.is_open()) {
            int help = 0;
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % 1000 == 0) {
                    adj.re_add_edges(new_edges);
                    trans.add_edges(new_edges);
//                    trans.caculate(i, 0, std::numeric_limits<time_t>::max());
//                    std::cout << "adj: " << adj.f.size() << " trans: " << trans.f.size() << std::endl;
                    if (adj.f.size() != trans.f.size()) {
//                        std::cout << "error size!!!!!!!!!!!!!" << std::endl;
                        std::cout << "adj: " << adj.f.size() << " trans: " << trans.f.size() << std::endl;
                    }
                    for (auto& [node, dis]: adj.f) {
                        if (trans.f.contains(node)) {
                            if (trans.f[node] != dis) {
                                std::cout << "error dis!!!!!!!!!!!!!" << std::endl;
                            }
                        } else {
                            std::cout << node << std::endl;
                            std::cout << "miss!!!!!!!!!!!!!" << std::endl;
                        }
                    }
                    std::cout << "finish " << m << std::endl;
                    new_edges.clear();
                }
            }
        }
    }
}

void delete_test1(std::string filename) {
    for (int i = 1; i < 100; i++) {
        i = 4902;
        ADJ adj(filename);
        OSE ose = adj.to_OSE();
        TRANS trans(filename);
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        trans.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (infile.is_open()) {
            int help = 0;
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % 1 == 0) {
                    adj.re_delete_edges(new_edges);
                    trans.delete_edges(new_edges);
//                    trans.caculate(i, 0, std::numeric_limits<time_t>::max());
                    if (adj.f.size() != trans.f.size()) {
                        std::cout << "error size!!!!!!!!!!!!!" << std::endl;
                    }
                    for (auto& [node, dis]: trans.f) {
                        if (adj.f.contains(node)) {
                            if (adj.f[node] != dis) {
                                std::cout << node << " " << dis << " " << adj.f[node] << std::endl;
                                std::cout << "error dis!!!!!!!!!!!!!" << std::endl;
                            }
                        } else {
                            std::cout << node << std::endl;
                            std::cout << "miss!!!!!!!!!!!!!" << std::endl;
                        }
                    }
                    std::cout << "finish " << m << std::endl;
                    new_edges.clear();
                }
            }
        }
    }
}

template <typename T>
void print_five_num_summary(int index, const std::vector<T>& v) {
    if (v.empty()) {
        return;  // 如果子 vector 为空，不输出
    }

    // 复制并排序原始 vector
    std::vector<T> sorted_v = v;
    std::sort(sorted_v.begin(), sorted_v.end());

    size_t n = sorted_v.size();

    // 计算五个分位数
    auto min = sorted_v.front();
    auto max = sorted_v.back();
    auto median = sorted_v[n / 2];
    auto lower_quartile = sorted_v[n / 4];
    auto upper_quartile = sorted_v[3 * n / 4];

    // 输出索引和五个分位数
    std::cout << index << " "
              << min << " "
              << lower_quartile << " "
              << median << " "
              << upper_quartile << " "
              << max << std::endl;
}

void final_add_test(std::string filename, int vnum, int mnum) {
    std::srand(unsigned(std::time(0)));
    ADJ adj(filename);
    std::vector<int> sf(adj.vertices.begin(), adj.vertices.end());
    std::random_shuffle(sf.begin(), sf.end());
    std::vector<std::vector<int>> hello(5);
    std::vector<std::vector<double>> hello1(3);
    for (int ii = 1; ii <= vnum; ii++) {
        int i = sf[ii];
        std::cout << "start=" << i << ":" << std::endl;
        std::ofstream outfile;
        outfile.open("digg"+ std::to_string(i) + "_" + std::to_string(mnum) + "_" "add.txt", std::ios::out | std::ios::trunc );
        std::ofstream outfile2;
        outfile2.open("digg"+ std::to_string(i) + "_" + std::to_string(mnum) + "_" "size.txt", std::ios::out | std::ios::trunc );
        ADJ adj("");
        ADJ readj("");
        OSE ose = adj.to_OSE();
        TRANS trans("");
        TRANS retrans("");
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        readj.caculate(i, 0, std::numeric_limits<time_t>::max());
        trans.caculate(i, 0, std::numeric_limits<time_t>::max());
        retrans.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (infile.is_open()) {
            size_t helpp = adj.dis.size();
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % mnum == 0) {
                    auto start = std::chrono::system_clock::now();
                    ose.add_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration1 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[0].push_back(duration1.count());
                    start = std::chrono::system_clock::now();
                    adj.add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration2 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[1].push_back(duration2.count());
                    start = std::chrono::system_clock::now();
                    readj.re_add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration3 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[2].push_back(duration3.count());
                    start = std::chrono::system_clock::now();
                    trans.add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration4 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[3].push_back(duration4.count());
                    start = std::chrono::system_clock::now();
                    retrans.re_add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration5 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[4].push_back(duration5.count());
                    new_edges.clear();
//                    std::cout << duration1 << " " << duration2 << " " << duration3 << " " << duration4 << " " << duration5 << std::endl;
                    hello1[0].push_back((double)(duration1.count()) / (duration2.count()));
                    hello1[1].push_back((double)(duration3.count()) / (duration2.count()));
                    hello1[2].push_back((double)(duration5.count()) / (duration4.count()));
                    outfile << duration1.count() << " " << duration2.count() << " " << duration3.count() << " " << duration4.count() << " " << duration5.count() << " " << adj.f.size() << std::endl;
                    int sz = 0;
                    for (auto [k, v]: adj.L) {
                        sz += v.size();
                    }
                    outfile2 << adj.f.size() << " " << sz << " " << trans.dis.size() << std::endl;
                    std::cout << "finish: " << m << std::endl;
                }
            }
        }
    }
    // 输出每个子 vector 的五个分位数
    std::cout << "Integer Vectors Summary:\n";
    for (int i = 0; i < hello.size(); ++i) {
        print_five_num_summary(i, hello[i]);
    }

    std::cout << "\nDouble Vectors Summary:\n";
    for (int i = 0; i < hello1.size(); ++i) {
        print_five_num_summary(i, hello1[i]);
    }
}

void final_delete_test(std::string filename, int vnum, int mnum) {
    std::srand(unsigned(std::time(0)));
    ADJ adj(filename);
    std::vector<int> sf(adj.vertices.begin(), adj.vertices.end());
    std::random_shuffle(sf.begin(), sf.end());
    std::vector<std::vector<int>> hello(5);
    std::vector<std::vector<double>> hello1(3);
    for (int ii = 1; ii <= vnum; ii++) {
        int i = sf[ii];
        std::cout << "start=" << i << ":" << std::endl;
        std::ofstream outfile;
        outfile.open("fb" + std::to_string(i) + "_" + std::to_string(mnum) + "_" "delete.txt", std::ios::out | std::ios::trunc );
        std::ofstream outfile2;
        outfile2.open("fb" + std::to_string(i) + "_" + std::to_string(mnum) + "_" "deletesize.txt", std::ios::out | std::ios::trunc );
        ADJ adj(filename);
        ADJ readj(filename);
        OSE ose = adj.to_OSE();
        TRANS trans(filename);
        TRANS retrans(filename);
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        readj.caculate(i, 0, std::numeric_limits<time_t>::max());
        trans.caculate(i, 0, std::numeric_limits<time_t>::max());
        retrans.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (infile.is_open()) {
            size_t helpp = adj.dis.size();
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % mnum == 0) {
                    auto start = std::chrono::system_clock::now();
                    ose.delete_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration1 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[0].push_back(duration1.count());
                    start = std::chrono::system_clock::now();
                    adj.delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration2 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[1].push_back(duration2.count());
                    start = std::chrono::system_clock::now();
                    readj.re_delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration3 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[2].push_back(duration3.count());
                    start = std::chrono::system_clock::now();
                    trans.delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration4 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[3].push_back(duration4.count());
                    start = std::chrono::system_clock::now();
                    retrans.re_delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    auto duration5 = duration_cast<std::chrono::microseconds>(end - start);
                    hello[4].push_back(duration5.count());
                    int cnt1 = 0;
                    for (auto& [node, dis]: adj.L) {
                        cnt1 += dis.size();
                    }
                    int cnt2 = trans.dis.size();
                    hello1[0].push_back((double)(duration1.count()) / (duration2.count()));
                    hello1[1].push_back((double)(duration3.count()) / (duration2.count()));
                    hello1[2].push_back((double)(duration5.count()) / (duration4.count()));
                    outfile << duration1.count() << " " << duration2.count() << " " << duration3.count() << " " << duration4.count() << " " << duration5.count() << " " << adj.f.size() << std::endl;
                    outfile2 << adj.f.size() << " " << cnt1 << " " << cnt2 << std::endl;
                    std::cout << "finish " << m << std::endl;
                    new_edges.clear();
                }
            }
        }

        std::cout << "end=" << i << " " << std::endl;
    }
    // 输出每个子 vector 的五个分位数
    std::cout << "Integer Vectors Summary:\n";
    for (int i = 0; i < hello.size(); ++i) {
        print_five_num_summary(i, hello[i]);
    }

    std::cout << "\nDouble Vectors Summary:\n";
    for (int i = 0; i < hello1.size(); ++i) {
        print_five_num_summary(i, hello1[i]);
    }
}



